The present invention relates generally to memory address generation and, more particularly, to modulo address generation for accessing circular buffers.
Circular buffers are used in a variety of useful applications to store data, such as coefficient data used in signal processing applications, for ordered retrieval.
Circular buffers may be implemented in a variety of ways in a variety of devices including processors, digital signal processors and digital signal controllers. One way is to use software program instructions to create a circular buffer within the memory of the device. The circular buffer may be addressed using modulo addressing This is typically done by designating space within the memory having upper and lower boundaries to be used as the buffer. The software then designates a current pointer to the memory which may be used for writing data into a memory location within the buffer specified by the pointer. The same or a separate pointer may be used to indicate a current memory location from which to read data.
During operation of a software-based modulo addressing scheme, the pointers are incremented (or decremented) after data is written into or read from a current location. The pointers are also checked against the upper and lower boundaries of the buffer. When any pointer falls outside of either the upper or lower boundary, the program causes that pointer to re-enter the buffer from the opposite side. To illustrate, when a pointer is incremented so that it specifies a memory location that is one or more locations below the lower boundary, the program changes the pointer value to specify the top of the buffer. When the pointer overflows the bottom boundary by more than one, the pointer is changed to the top of the buffer plus an offset that reflects the amount of overflow out the bottom.
In general, it is inefficient to implement circular buffers in software because of the software overhead associated with changing pointer values and generating xe2x80x9cwrap aroundxe2x80x9d addresses after an overflow. For this reason, modulo addressing schemes have been implemented in hardware on processor chips. These schemes have the advantage of being fast but the disadvantage or requiring additional circuitry on the processor to implement.
Various modulo addressing circuits and hardware schemes have been proposed. According to some schemes, when an overflow of the circular buffer occurs out of one side of the buffer, the amount of overflow is added to the length of the buffer and this sum is added to either the start or the end address depending on the side out of which the overflow occurred. In other schemes, comparators are implemented to check each proposed address against either or both of an upper or lower address value to determine when an overflow has occurred. In still other schemes, a current address is broken down into a base address and an offset value which is used to determine a position within a buffer.
There is a need for a new hardware based modulo addressing scheme that is hardware based and fast but requires only a small amount of logic to implement.
According to embodiments of the present invention, a hardware-based modulo addressing scheme that is fast and makes efficient use of logic is proposed. The scheme relies on a subtractor, multiplexers and AND/OR logic to produce modulo addresses to address, for example, a circular buffer in a memory. The buffer is defined by the user based on start and end addresses and an offset value. The offset may be positive or negative and may be greater than one.
According to one embodiment, a modulo addressing circuit includes registers, an adder, a subtractor, OR logic and a multiplexer. The registers store a pointer, an offset, an end address and a start address. The adder determines a sum of the pointer and the offset and the subtractor determines a carry and the difference between the sum and a selected one of the start and end addresses. The OR logic calculates a logical OR between the difference and the selected address. The multiplexer uses either the sum or the logical OR as the next modulo address based on the carry signal output by the subtractor.
The multiplexer may store the sum into the pointer when the carry signal does not indicate an overflow. The circuit may further include AND logic for calculating a logical AND between the difference and the selected address and a multiplexer for storing the logical AND into the pointer when the carry signal indicates an overflow out of the start address. A mode bit may determine the selected address as either the start or the end address.
According to another embodiment of the invention, a method of generating modulo addresses includes calculating a sum of a current address and an offset. A start address is subtracted from the sum to determine a difference and a carry. A logical OR is generated between the difference and the start address and either the sum or the logical OR is selected as a new current address based on the carry.
According to still another embodiment of the invention, a method of generating modulo addresses includes calculating a sum of a current address and an offset. An end address is subtracted from the sum to determine a difference and a carry. A logical AND is generated between the difference and the end address and either the sum or the logical AND is selected as a new current address based on the carry. The method may further include using the new current address to access a buffer within a memory. The method may further include saving the new current address as the current address.